#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-30 3:52 下午
# @Author  : yangdy
# @File    : Heap
# @Software: PyCharmCE

class Heap:
    def __init__(self, data=None, key=None, reverse=False):
        self.data = data if data is not None else []
        self.key = key
        self.reverse = reverse
        if len(self.data) > 0:
            for i in range(len(self.data)//2, -1, -1):
                self.down(i)

    def _cmp(self, x, y):
        if self.key:
            x, y = self.key(x), self.key(y)
        return x < y if not self.reverse else x > y

    def clear(self):
        self.data = []

    def down(self, index=0):
        i, x, ll = index, index * 2 + 1, len(self.data)
        if x >= ll:
            return
        while x < ll:
            x += 0 if x+1 >= ll or self._cmp(self.data[x+1], self.data[x]) else 1
            if self._cmp(self.data[i], self.data[x]):
                self.data[x], self.data[i] = self.data[i], self.data[x]
                i, x = x, x * 2 + 1
            else:
                break

    def up(self, index=0):
        if index <= 0:
            return
        i, x = index, (index - 1) // 2
        while i > 0 and self._cmp(self.data[x], self.data[i]):
            self.data[x], self.data[i] = self.data[i], self.data[x]
            i, x = x, (x - 1) // 2

    def top(self):
        return self.data[0] if len(self.data) > 0 else None

    def is_empty(self):
        return len(self.data) <= 0

    def insert(self, x):
        self.data.append(x)
        self.up(len(self.data)-1)

    def pop(self):
        if self.is_empty():
            return
        ans = self.data[0]
        last = self.data.pop()
        if not self.is_empty():
            self.data[0] = last
            self.down()
        return ans
